package Class032_LinkedListQuestions;

import BasicDataStructures.ListNode;
import Utils.ListUtils;

import java.util.HashMap;

//链表题是练习coding的好题
//往往用容器会变得非常简单好想，但是不用容器比较难
//要有思路，还能用代码实现

//左神关于dummyHead问题的解读:
/*
* 工程上的实现，一个类型的初始化函数可能很复杂，并不像刷题中的节点可以随意构造，此时你要怎么办？
* 工程上的节点初始化的时候，内存占用可能很大，并不像刷题中的节点代价那么少，此时你要怎么办？
* 不用假节点，目的是基于这样一种追求：
* 一个结构的事情，就在这个结构自身上做调整，解决这个结构自身的问题，而不是再引入外部的东西。
* */
public class LinkedListQuestions {
    public static void main(String[] args) {
//        int[] l = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
//        int k = 6;
//        ListNode head = ListUtils.generateList(l);
//        ListUtils.printList(head);
//        ListNode newHead = reversePerKGroup(head, k);
//        ListUtils.printList(newHead);
//
//        ListNode newList = copyListWithRandomPtNoMap(newHead);
//        ListUtils.printList(newList);
//
//        l = new int[]{1, 2, 3, 4, 5, 6, 7, 8};
//        ListNode h = ListUtils.generateList(l);
//        System.out.println(isPadLinkedList(h));
//        ListUtils.printList(h);
//
//        h = adjustList(h);
//        ListUtils.printList(h);
        int[] arr = {1,3,4,-1,2,-3};
        ListNode head = ListUtils.generateList(arr);
        System.out.println("Before sort:");
        ListUtils.printList(head);
        ListNode newHead = sortList(head);
        System.out.println("After sort:");
        ListUtils.printList(newHead);
    }

    //找交点
    public static ListNode getIntersectionNode(ListNode n1, ListNode n2) {
        if (n1 == null || n2 == null) {
            return null;
        }
        int n1Length = 0, n2Length = 0;
        ListNode t1 = n1, t2 = n2;
        while (t1 != null) {
            n1Length++;
            t1 = t1.next;
        }
        while (t2 != null) {
            n2Length++;
            t2 = t2.next;
        }
        ListNode longer = n1Length >= n2Length ? n1 : n2;
        ListNode shorter = n1Length >= n2Length ? n2 : n1;
        int preSteps = Math.abs(n1Length - n2Length);
        while (preSteps > 0) {
            longer = longer.next;
            preSteps--;
        }
        while (longer != null && shorter != null) {
            if (longer == shorter) return longer;
            longer = longer.next;
            shorter = shorter.next;
        }
        return null;
    }

    //用更少的变量
    public static ListNode getIntersectionNode2(ListNode n1, ListNode n2) {
        if (n1 == null || n2 == null) {
            return null;
        }
        int diff = 0;
        ListNode a = n1, b = n2;
        while (a != null) {
            diff++;
            a = a.next;
        }
        while (b != null) {
            diff--;
            b = b.next;
        }

        if (diff >= 0) {
            a = n1;
            b = n2;
        } else {
            a = n2;
            b = n1;
        }
        diff = Math.abs(diff);
        while (diff > 0) {
            a = a.next;
            diff--;
        }
        while (a != null && b != null) {
            if (a == b) return a;
            a = a.next;
            b = b.next;
        }
        return null;
    }

    //每K个节点一组，反转链表
    //不足3个的，维持原样
    //用数组容器
    public static ListNode reverseKGroupsUsingArray(ListNode head, int k) {
        ListNode cur = head;
        int total = 0;
        while (cur != null) {
            total++;
            cur = cur.next;
        }
        ListNode[] nodes = new ListNode[total];
        for(int i = 0; i < total; i++) {
            nodes[i] = head;
            head = head.next;
        }
        for(int i = 0; i + k - 1 < total; i+=k) {
            int L = i, R = i + k - 1;
            while(L < R) {
                ListNode temp = nodes[L];
                nodes[L] = nodes[R];
                nodes[R] = temp;
                L++;
                R--;
            }
        }
        for(int i = 0; i < total - 1; i++) {
            nodes[i].next = nodes[i + 1];
        }
        nodes[total - 1].next = null;
        return nodes[0];
    }

    //不用数组容器
    public static ListNode reversePerKGroup(ListNode head, int k) {
        ListNode cur = head;
        int total = 0;
        while (cur != null) {
            total++;
            cur = cur.next;
        }
        if(total < k) {
            return head;
        }
        ListNode newHead = null;
        ListNode preTail = null;
        ListNode next = head;
        while (total >= k) {
            ListNode[] info = reverseK(next, k);
            if(preTail == null) {
                newHead = info[0];
            }else {
                preTail.next = info[0];
            }
            preTail = info[1];
            next = info[2];
            total -= k;
        }
        preTail.next = next;
        return newHead;
    }

    //[0]: head
    //[1]: tail
    //[2]: next
    private static ListNode[] reverseK(ListNode cur, int k) {
        ListNode t = cur;
        ListNode next = null;

        ListNode pre = null;
        while (k > 0) {
            k--;
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return new ListNode[]{pre, t, next};
    }

    //复制带有随机指针的链表
    //使用哈希表辅助
    //k:origin node  v:copied node
    //第一遍遍历，把节点先拷贝不设置指针
    //再遍历map，能找到对应原始节点的相应指针
    public static ListNode copyListWithRandomPt(ListNode head) {
        HashMap<ListNode, ListNode> copyMap = new HashMap<>();
        ListNode newHead = new ListNode(head.val);
        copyMap.put(head, newHead);
        head = head.next;
        while(head != null) {
            ListNode copied = new ListNode(head.val);
            copyMap.put(head, copied);
            head = head.next;
        }
        for (ListNode origin : copyMap.keySet()) {
            ListNode copied = copyMap.get(origin);
            copied.next = origin.next == null ? null : copyMap.get(origin.next);
            copied.random = origin.random == null ? null : copyMap.get(origin.random);
        }
        return newHead;
    }

    //不用哈希表辅助，利用node本身的next指针作为记录
    public static ListNode copyListWithRandomPtNoMap(ListNode head) {
        if(head == null) return null;
        ListNode originNext = null;
        ListNode cur = head;
        while(cur != null) {
            originNext = cur.next;
            cur.next = new ListNode(cur.val);
            cur.next.next = originNext;
            cur = originNext;
        }
        cur = head;
        ListNode ans = cur.next;
        while(cur != null) {
            cur.next.random = cur.random == null ? null : cur.random.next;
            cur = cur.next.next;
        }
        cur = head;
        while(cur != null) {
            originNext = cur.next.next;
            cur.next.next = originNext == null ? null : originNext.next;
            cur.next = originNext;
            cur = originNext;
        }
        return ans;
    }

    //判断链表是否为回文
    //用栈非常简单
    //如何不用栈？
    //技巧：快慢指针
    public static boolean isPadLinkedList(ListNode head) {
        if(head == null || head.next == null) return true;
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode rightEnd = reverse(slow);
        ListNode R = rightEnd;
        boolean res = true;
        while(head != null && R != null) {
            if(head.val != R.val) {
                res = false;
                break;
            }
            head = head.next;
            R = R.next;
        }
        reverse(rightEnd);
        return res;
    }

    private static ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode next = null;
        while(head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    //考研常考题:
    //Suppose a linked list is in the form of:
    //1 -> 2 -> 3 -> 4 -> 5 -> 6
    //You need to adjust it to :
    //1 -> 6 -> 2 -> 4 -> 3 -> 5
    //思路: 快慢指针找中点，右边逆序
    public static ListNode adjustList(ListNode head) {
        if(head == null || head.next == null || head.next.next == null) {
            return head;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode r = reverse(slow);
        ListNode l = head;
        ListNode originalLeftNext = null;
        ListNode originalRightNext = null;
        while(l != null && l != r) {
            originalLeftNext = l.next;
            originalRightNext = r.next;
            l.next = r;
            r.next = originalLeftNext;
            l = originalLeftNext;
            r = originalRightNext;
        }
        return head;
    }

    //一个链表可能有环
    //如果存在环，返回入环节点，否则返回null
    //用容器很简单，边遍历边放入set，看之前存在过没有
    public static ListNode isCycleList(ListNode head) {
        if(head == null || head.next == null) return null;
        if(head.next == head) return head;
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(fast == slow) break;
        }
        if(fast.next == null || fast.next.next == null) {
            return null;
        }
        fast = head;
        while(fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    // 如何排序一个链表，满足:
    // T: O(N * logN), S: O(1), meanwhile stable
    // 为什么数组的merge无法做到空间复杂度O(1)?
    // 因为merge的时候需要辅助数组，用来调整好组内的相对次序再放回去
    // 但是链表是否需要辅助数组，先把节点存入?
    // 不需要，因为有next指针，直接依次往后挂载就行
    // 所以核心思想还是merge，只是每一组怎么操作就是细节处理
    public static ListNode sortList(ListNode head) {
        if(head == null) return null;
        if(head.next == null) return head;
        int total = 0;
        ListNode cur = head;
        while(cur != null) {
            total++;
            cur = cur.next;
        }
        ListNode groupHead = head;
        ListNode preTail = null;
        ListNode totalHead = head;
        for(int group = 1; group < total; group <<= 1) {
            while(groupHead != null) {
                ListNode[] info = getMergeInfo(groupHead, group);
                ListNode[] hAndT = mergeGroup(info[0], info[1], info[2], info[3]);
                if (preTail != null) {
                    preTail.next = hAndT[0];
                } else {
                    totalHead = hAndT[0];
                }
                preTail = hAndT[1];
                groupHead = info[4];
//                ListUtils.printList(totalHead);
            }
            groupHead = totalHead;
            preTail = null;
        }
        return totalHead;
    }

    // [0]: ls
    // [1]: le
    // [2]: rs
    // [3]: re
    // [4]: next
    public static ListNode[] getMergeInfo(ListNode cur, int groupSize) {
        ListNode ls = cur, le = null;
        ListNode rs = null, re = null;
        ListNode next = null;
        int no = 1;
        while(cur != null && no <= groupSize * 2) {
            if(no <= groupSize) {
                le = cur;
            }
            if(no == groupSize + 1) {
                rs = cur;
            }
            if(no >= groupSize + 1 && no <= groupSize * 2) {
                re = cur;
            }
            cur = cur.next;
            no++;
        }
        next = re == null ? null : re.next;
        return new ListNode[] {ls, le, rs, re, next};
    }

    public static ListNode[] mergeGroup(ListNode ls, ListNode le, ListNode rs, ListNode re) {
        if(rs == null) return new ListNode[] {ls, le};
        ListNode l = ls, r = rs;
        ListNode pre = null;
        ListNode cur = null;
        ListNode head = null;
        while(l != le.next && r != re.next) {
            if(l.val <= r.val) {
                cur = l;
                l = l.next;
            }else {
                cur = r;
                r = r.next;
            }
            if(pre != null) {
                pre.next = cur;
            }else {
                head = cur;
            }
            pre = cur;
        }
        if(l != le.next) {
            while (l != le.next) {
                pre.next = l;
                pre = l;
                l = l.next;
            }
        }else {
            while (r != re.next) {
                pre.next = r;
                pre = r;
                r = r.next;
            }
        }
        pre.next = null;
        return new ListNode[] {head, pre};
    }
}
